\documentclass[revision]{FPSAC2017}

\articlenumber{37}
\addbibresource{37_Chapoton_Nadeau.bib}

\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{arrows,trees}

\newtheorem{theorem}{Theorem}%[section] 
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{lemma}[theorem]{Lemma} 
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{example}[theorem]{Example} 
\newtheorem{problem}[theorem]{Problem} 
\newtheorem{algorithm}[theorem]{Algorithm} 
\numberwithin{equation}{section}

\title{Combinatorics of the categories of noncrossing partitions}

\author[F. Chapoton, P. Nadeau]{Fr\'ed\'eric Chapoton\addressmark{1} \and Philippe Nadeau\addressmark{2}}

\address{\addressmark{1}Universit\'e de Strasbourg, CNRS, IRMA UMR 7501, F-67000 Strasbourg, France\\ \addressmark{2}Universit\'e de Lyon, CNRS UMR 5208, F-69622 Villeurbanne Cedex, France\\}

\received{\today}

% anneaux
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}

% categories
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\NC}{\mathtt{NC}}

% symboles
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\Cat}{\operatorname{Cat}}
\newcommand{\liste}{\operatorname{List}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\bL}{\mathbb{L}}
\renewcommand{\hom}{\operatorname{Hom}}
\newcommand{\Bic}{\mathcal{BIC}}

% Dynkin
\newcommand{\TA}{\mathbb{A}}
\newcommand{\TD}{\mathbb{D}}
\newcommand{\TE}{\mathbb{E}}

% q-binomiaux
\newcommand{\qbinom}[2]{\genfrac{[}{]}{0mm}{1}{#1}{#2}}
\newcommand{\qbase}[3]{\genfrac{[}{]}{0mm}{1}{#1,\,#2}{#3}}
\newcommand{\sti}[2]{\genfrac{\{}{\}}{0mm}{1}{#1}{#2}}

\newcommand*\pFq[4]{{}_{#1}\phi_{#2}\biggl(\genfrac..{0pt}{}{#3}{#4};q,q\biggr)}

\abstract{We obtain an alternative combinatorial description of Igusa's
  cubical categories of noncrossing partitions, using various classes of trees. We also count the morphisms in these categories,  according to the ranks of the source and target objects.}

\resume{Nous obtenons une description combinatoire alternative des cat\'egories cubiques de partitions non-crois\'ees d'Igusa, en utilisant diverses classes d'arbres. Nous comptons aussi le nombre de morphismes dans ces cat\'egories selon les rangs des objets source et cible.}

\keywords{noncrossing partitions, picture group, plane trees,  Schr\"oder trees}


\begin{document}
\maketitle
\section*{Introduction}
Kiyoshi Igusa has introduced in~\cite{igusa} interesting category
of noncrossing partitions $\NP_n$, one for each $n\geq 1$. The objects of the category $\NP_n$ are noncrossing partitions of the set $\{1,2,\dots,n\}$ and morphisms are defined using forests of binary trees. This construction was
motivated by the general theory of pictures and picture groups, that
can be associated to quivers of finite type. The category of
noncrossing partitions is closely related to the special case of the
equi-oriented quiver of type $A_n$.

This article started with the idea of counting the morphisms in this
category. It turns out that there is a nice answer. For our
convenience, we will let $\NP_n$ be the opposite category of the
category introduced by Igusa.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.5\textwidth]{noncrossing_inline.pdf}
  \caption{A noncrossing partition of $\{1,\dots,22\}$ in $10$ blocks}
  \label{inline}
\end{figure}

A partition $\pi=\{\pi_1,\ldots,\pi_k\}$ of a linearly ordered set is called \emph{noncrossing} if given any two blocks $\pi_i\neq\pi_j$ of $\pi$, there does not exist $a,b$ in $\pi_i$ and $c,d$ in $\pi_j$ such that $a<c<b<d$. We let $\NC_n$ be the set of noncrossing partitions of $\{1,\cdots,n\}$, and we represent them by a diagram with the numbers $1, 2, \dots,n$ from
left to right on an horizontal line, as in \cref{inline}.

Let the rank $\rk(\pi)$ of a noncrossing partition $\pi$ be $n$ minus
the number of blocks of $\pi$.  The bottom noncrossing partition
$\{1\},\{2\},\dots,\{n\}$ has rank $0$ and the top noncrossing
partition $\{1,2,\dots,n\}$ has rank $n-1$. Then morphisms in $\NP_n$
can only increase the rank. Every morphism is a composition of
morphisms increasing the rank by $1$. This category is therefore
graded by the rank.
\smallskip

The total number of morphisms in $\NP_n$ is given for small $n \geq 1$ by 
\begin{equation*}
  1, 4, 21, 126, 818, 5594, 39693, 289510, \dots
\end{equation*}
which is the sequence \href{http://oeis.org/A003168}{A3168}
in the OEIS encyclopedia. These numbers count dissections of polygons
into even regions, and are also the number of sylvester classes of
$2$-packed words, see eq. (184) in~\cite{novellithibon}.

To refine this enumeration, one can count morphisms according to the difference of ranks between their source and their target. The numbers for $n=1,\ldots, 5$ are:
\begin{equation}
  (1),\quad  (2,2),\quad (5,11,5), \quad   (14,49,49,14), \quad   (42,204,326,204,42).
\label{sym2}
\end{equation}
Note the symmetry of these numbers, which is not obviously induced by
a symmetry of the category. 

These numbers are related to the fact that the category $\NP_n$ is a
cubical category, as explained in~\cite{igusa}. This implies that one can
describe a classifying space for $\NP_n$ which is a cubical complex, in
which the number of $k$-cubes is exactly the number of morphisms in
$\NP_n$ increasing the rank by $k$. The symmetry observed in~\eqref{sym2} may have a topological
explanation by mean of this cubical complex, but this is not clear to us.

To refine even further the enumeration, one can count all morphisms
whose source and target have fixed ranks. This gives triangles of
numbers, the first few ones being
\begin{equation*}
  \left(\begin{array}{r}1\end{array}\right),
\quad
  \left(\begin{array}{rr}2 & 1 \\1 & \end{array}\right),
\quad
  \left(\begin{array}{rrr}5 & 5 & 1 \\6 & 3 &  \\1 &  & \end{array}\right),
\quad
  \left(\begin{array}{rrrr}14 & 21 & 9 & 1 \\28 & 28 & 6 &  \\12 & 6 &  &  \\1 &  &  & \end{array}\right).
\end{equation*}

Let $\ell_{i,j}$ be the number of morphisms from rank $i$ to rank $j$.
\begin{theorem}
\label{th:refined_enumeration}
Let $n,i,j$ satisfy $0\leq i \leq j \leq n-1$. Then
\begin{equation}
  \label{formule_cij}
  \ell_{i,j} = \frac{1}{n}\binom{n}{i}\binom{n}{j+1}\binom{2n-i}{j-i}.
\end{equation}
\end{theorem} 

It follows that the three border layers of these triangles of numbers
are given by the Narayana numbers
(seq. \href{http://oeis.org/A1263}{A1263}) for the diagonal, by
sequence \href{http://oeis.org/A108767}{A108767} for the left column
and by sequence \href{http://oeis.org/A33282}{A33282} (counting
dissections of a regular polygon according to the number of regions, see~\cite{flajoletnoy}) for the top row.


Let now $\bL_n(u,v),  \Delta_n(u,v) $ be the generating polynomials
\begin{equation*}
  \bL_n(u,v) = \sum_{0 \leq i \leq j\leq n-1} \ell_{i,j} u^i v^j\quad\text{ and }\quad \Delta_n(u,v) = \bL_n(u-1,v).
\end{equation*}

This change of variables allows to exhibit in $\Delta_n$ a hidden
ternary symmetry of $\bL_n$. We will prove in \cref{sub_symmetry} that $\Delta_n$ is a
generating polynomial for ternary rooted trees with parameters their
numbers of left and right edges (In particular, the values
$\Delta_n(1,1)$ form the sequence \href{http://oeis.org/A1764}{A1764}). This implies immediately that  $\Delta_n$ has the
following symmetries:
\begin{align*}
  \Delta_n(u,v) &= (uv)^{n-1} \Delta_n(1/v, 1/u),\\
  \Delta_n(u,v) &= v^{n-1} \Delta_n(uv,1/v).
\end{align*}
It follows that
\begin{equation*}
  u^{n-1} \bL_n(v,1/u) = \bL_n((v+1-u)/u,u).
\end{equation*}
By letting $v=u=x$, one gets that
\begin{equation*}
  x^{n-1} \bL_n(x,1/x) = \bL_n(1/x,x)
\end{equation*}
which is the symmetry observed in~\eqref{sym2}.

\medskip

A remark can be made about the Euler characteristic of the categories
$\NP_n$. This is just $\chi(\NP_n) = (-1)^{n-1} \bL_n(-1,-1)$ 
because of the known description of the classifying space as a cubical complex. It
turns out to give the aerated Catalan numbers:
\begin{equation}
  1, 0, -1, 0, 2, 0, -5, 0, 14, 0, -42, 0, 132, 0, -429, 0, 1430, \dots
\end{equation}
The full homology of the classifying space of $\NP_n$ has been
computed in terms of ballot numbers in~\cite{igusa_orr_etc}.

The paper is organized as follows: in the first section, we obtain an
alternative, and somewhat simpler, description of the categories
$\NP_n$. This is based on the combinatorics of Schr\"oder trees, with an
intermediate step using a description of noncrossing partitions by
bicolored trees. The second and last section uses this description and
a method from free probability to obtain the enumerative results explained above.
\bigskip

Formula~\eqref{formule_cij} was found during the first author's
stay in Seoul in December 2014. F. Chapoton has benefited from the support of the project Carma of the French ANR (ANR-12-BS01-0017).

\section{A combinatorial model of the category}
\label{sec:combi}

Let us sketch an overview of Igusa's construction, see  \cite{igusa}; to compare with his notations we stress that we use the opposite category. The objects of the category $\NP_n$ are noncrossing partitions of size $n$. Then one attaches a  set of edges $E(\pi)$
to every $\pi$, and more generally a relative edge set $E(\pi,\mu)$ if $\pi$ refines $\mu$. Morphisms are then defined as certain subsets of $E(\pi,\mu)$, and
their composition uses a certain notion of compatibility of edges. Igusa
proceeds to prove that one thus obtains a \emph{cubical category} with
properties ensuring that its classifying space $\mathcal{BNP}(n)$ is a
$K(\pi,1)$ space. Then the fundamental group of $\mathcal{BNP}(n)$ is
computed and seen to be equal to the \emph{picture group}
$G(A_{n-1})$.

The construction of the category  $\NP_n$ uses heavily the language of vector spaces and linear maps. In this section we reformulate it using the language of trees, which gives a pleasant description of morphism composition in particular.

\subsection{Objects}

Let $\Bic_n$ be the set of plane rooted trees with $n$ edges, canonically endowed with a bipartite black and white coloring in which the root is white. Our starting point is to encode $\pi\in\NC_n$ with a tree $t(\pi)\in\Bic_n$ as follows. Black vertices of $t(\pi)$ correspond to blocks of $\pi$, while white vertices are associated to consecutive entries of a block, and an extra one. Black to white edges go from a block to its consecutive entries, while white to black edges go to the maximal blocks between the consecutive entries. The extra white vertex on top is the root, and has edges to the maximal blocks.

This can be conveniently depicted when the noncrossing partition is drawn as in \cref{inline,fig:arbre}. Namely, one can put a black vertex at the middle of the unique top arch of every block, and a white vertex at the middle of every bottom arch of every block. The additional white vertex can be put above all the other vertices.

\begin{proposition}[{\cite[Theorem 2.1]{GouldenJackson}}] The correspondence $\pi\to t(\pi)$ is a bijection from  $\NC_n$ to $\Bic_n$ such that the number of blocks of $\pi$ is equal to the number of black vertices of $t(\pi)$.
\end{proposition}

Note that the result in~\cite{GouldenJackson} is stated in terms of permutations. To connect it with our formulation, recall that  noncrossing partitions can be identified with minimal factorizations of the cyclic permutation $(1,2,\dots,n)$ as a product of two permutations (see~\cite{biane}).

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.7\textwidth]{noncrossing_arbre.pdf}
  \caption{Correspondence: noncrossing partition and bicolored plane tree}
  \label{fig:arbre}
\end{figure}



To recover the noncrossing partition $\pi$ from the tree $t(\pi)$, perform a counterclockwise tour of the tree, starting at the root. During this tour, every edge will be covered exactly once in each direction. Label the ``white to black'' edges by $1,2,\ldots, n$ in the order in which they are traversed during the tour. Then the labels around a black vertex form a block of the noncrossing partition $\pi$. \medskip

Let us give the correspondence between our setting and some notations
of~\cite[\S 1]{igusa}. A \emph{parallel set} of $\pi$ corresponds to a subset of blocks which are
children of a given white vertex in $t(\pi)$. The \emph{edge set $E(\pi)$}
corresponds to all pairs of black vertices of $t(\pi)$ which are adjacent to the
same white vertex


\subsection{Morphisms}
\label{sub_morphisms}
Let $\pi,\mu\in\NC_n$. There exists a morphism from $\pi$ to $\mu$ if and only if $\pi$ is a \emph{refinement} of $\mu$: this means that every block of $\pi$ is contained in a block of $\mu$, and  write this as $\pi\preceq \mu$.

Assume $\pi\preceq \mu$, and let $(\mu_1,\dots,\mu_k)$ be the blocks of $\mu$.  Let $\pi^j$ be the noncrossing partition induced by $\pi$ on the block $\mu_j$, which can be naturally considered as a single block partition. A \emph{morphism from $\pi$ to $\mu$} is defined as a collection of morphisms from $\pi^j$ to $\mu_j$ for $j=1,\dots,k$. 

In words, a general morphism from $\pi$ to $\mu$ can be recovered from morphisms between smaller noncrossing partitions with target a noncrossing partition with one block, together with $\mu$ serving as a pasting scheme. This will allow us to use methods of free probability to count all morphisms, starting from the knowledge of morphisms to single block partitions, see \cref{free_proba}.

It is thus enough to define morphisms to the top partition
$\{1,2,\ldots,n\}$, which we will call \emph{morphisms to the top} for
short. A \textit{binary tree} $B$ is a rooted planar binary tree,
defined recursively as either empty or a root vertex and a pair (left
subtree, right subtree). Its \emph{size} is its number of vertices. In
bicolored plane trees, we let $d(w)$ be the number of children of a
vertex $w$. The following definition is illustrated in \cref{toschroeder}, left.

\begin{definition}[\cite{igusa}]
\label{defi_morphisms}
A morphism from $\pi$ to the top is a collection of binary trees $(B_w)_w$ indexed by the white vertices $w\in t(\pi)$, where $B_w$ has size $d(w)$ .
\end{definition}


\begin{remark} An important remark is that the vertices of $B_w$ are naturally indexed by the blocks of $\pi$ corresponding to the $d(w)$ children of $w$. For this, perform an \emph{infix traversal} of $B_w$, by recursively running through its vertices $B_w$ in the order: left subtree, then root, then right subtree,  and labeling the vertices with blocks along the way. In this manner one sees that \cref{defi_morphisms} is the same as Igusa's.
\end{remark}

\begin{example}
\label{extremalmorphisms}
There is a single morphism from $\{1,\ldots,n\}$ to itself (which must therefore be the identity). By the definition of a general morphism, there is also a single morphism from $\pi$ to $\pi$ for any $\pi\in\NC_n$. Since morphisms only go from a partition to a coarser one, it follows that there are $|\NC_n|$ morphisms with the same starting and ending ranks. 

 Now consider the bottom partition $\pi_b=\{\{1\},\{2\},\ldots,\{n\}\}$. The tree $t(\pi_b)$ is a single white vertex with $n$ children, so morphisms from $\pi_b$ to the top are \emph{binary trees} with $n$ vertices. These are counted by Catalan numbers, which also enumerates $\NC_n$. This shows that in each of the rows of \eqref{sym2} the leftmost and rightmost numbers are equal to the same Catalan number.  A more general symmetry will be proved in \cref{sub_symmetry}.
\end{example}

We will now explain how to encode these morphisms by \emph{Schr\"oder trees}, \emph{i.e.} plane rooted trees with no vertex of degree $1$. So vertices are either leaves or \emph{inner vertices} of degree at least $2$. To each inner vertex of out-degree $d$ are attached $d-1$ \emph{angular sectors} formed by consecutive outgoing edges. Note that if a Schr\"oder tree has $n$ angular sectors then it has $n+1$ leaves. 

Let $\pi\in\NC_n$ and $t(\pi)\in\Bic_n$ its bicolored tree. Fix a morphism $f$  from $\pi$ to the top, which by definition is a binary tree $B_w$ of size $d(w)$ for each white vertex $w\in t(\pi)$. 

Let us give a recursive construction of the Schr\"oder tree $S(f)$, illustrated by \cref{toschroeder}. First consider the binary tree $B_r$  corresponding to the root $r$ of $t(\pi)$. As explained after \cref{defi_morphisms}, the vertices of $B_r$ correspond to black vertices $b_i$ of $t(\pi)$ of outdegrees $d_i$. Add outgoing edges to each $b_i$ in $B_r$ so that its outdegree becomes $d_i+2$, where the possible left or right edges present in $B_r$ must remain on the left or right. This results in  a tree $B'_r$, see \cref{toschroeder}. 

  Now each vertex $b_i$ has plane trees $t_i^j\in \Bic$ attached to it in $t(\pi)$ with $j=1,\ldots,d_i$. By restriction each comes equipped with some of the binary trees $B_w$ and thus determines a morphism. By induction, we know how to associate with each such morphism a Schr\"oder tree $S_i^j$. We then graft this tree at the end of $j$th inner edge of the vertex $b_i$ in $B'_r$, respecting the left-to-right ordering to get the desire $S(f)$.
\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{MorphismsToSchroeder}
  \caption{A morphism $f=(\pi,(B_w)_w)$ and the associated Schr\"oder tree $S(f)$. All labelings are canonical and deduced from specific traversals of the trees. }
  \label{toschroeder}
\end{figure}
\begin{proposition}
\label{bij_schroder}
  The correspondence $f\to S(f)$ is a bijection between morphisms from any element $\pi$ of $\NC_n$ to $\{1,\ldots, n\}$, and Schr\"oder trees with $n$ angular sectors. Inner vertices of $S(f)$ are in bijection with blocks of $\pi$, and an inner vertex has degree $d+1$ if the corresponding block has size $d$. 
\end{proposition}

\begin{proof}
By construction, the tree $S(f)$ is a Schr\"oder tree with $n$ angular sectors, so the correspondence is well-defined. We give the inverse bijection, and leave the easy details to the reader.  Given $S$ a Schr\"oder tree with $n$ angular sectors, let us construct $\pi\in \NC_n$ and a morphism $f$ from $\pi$ to the top. First, perform a tour of the tree $S$, and label the angular sectors encountered on the way by $1$ to $n$. The blocks of $\pi$ are then read off under the inner vertices. Now in $S$ only consider edges between inner vertices which are either the leftmost or rightmost ones. The connected components of the induced subgraph are binary trees which determine the morphism $f$.
\end{proof}

By the previous proposition and the description of morphisms in general, a morphism with target $\mu$ will be encoded with a collection $S(g)=(S(g)^{\mu_i})_i$ indexed by the blocks of $\mu$. For instance the morphism $f$ in the middle of \cref{examplecomposition} has target \{\{1,7,8,9\},\{2,3\},\{4,5\},\{6\},\{10,11,12\}\}.\medskip


There is a direct way to connect the tree $S(f)$ to what Igusa calls the ``rooted tree $[T]$ generated by a morphism''. Indeed $[T]$ is the tree formed by the \emph{inner edges} of $S(f)$ (that is to say, the edges between inner vertices), where inner vertices are labeled by their associated blocks. Equivalently, it is obtained by pruning all leaves of $S(f)$.


\subsection{Composition of morphisms}
\label{composition}

Suppose that one has a morphism $f$ from $\pi$ to $\mu$ and then $g$
from $\mu$ to the top. By \cref{bij_schroder}, $g$ corresponds to a Schr\"oder tree $S(g)$ where the vertices $b_{\mu_i}$ are indexed by the blocks $\mu_i$ of $\mu$, while $f$ corresponds to a collection of Schr\"oder trees $S(f)^{\mu_i}$, one for each block of $\mu$. Then the composition $g\circ f$ is determined as follows: in the Schr\"oder tree of $g$, replace   each vertex $b_{\mu_i}$ by the Schr\"oder tree $S_f(\mu_i)$. The resulting Schr\"oder tree is a Schr\"oder tree $S(h)$ and one defines  $g\circ f:=h$.

For the general case when the target of $g$ is a noncrossing
partition $\nu$, one simply extends the definition by applying the same
rule on every block of $\nu$.
\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{Composition}
  \caption{Composition of morphisms as a substitution in trees.}
  \label{examplecomposition}
\end{figure}


This composition of morphisms is closely related to an operad
structure on Schr\"oder trees, defined similarly using substitution
around vertices. This differs from the free operad structure used in
\cite{ncf_cumulants} in terms of grafting on leaves.  \medskip

Let us just say a few words (not going into details) on how to identify this simple composition with the original, convoluted description of the composition in the category $\NP_n$ in~\cite{igusa}. There the composition of morphisms is defined using a notion of compatibility on the relative edge sets $E(\pi, \mu)$, and morphisms are identified with maximal compatible subsets of edges.

Then the composition $g \circ f$ is given as the disjoint union of the edges of $g$ and the image of the edges of $f$ by a natural isomorphism. With some care, this can be seen to coincide with our substitution procedure, where the inner edges of $S(g\circ f)$ either come from the original inner edges of $S(g)$ or from inner edges of $f$. 
We now give two applications of our pictorial description of $\NP_n$:\bigskip 

\noindent\textbf{Composition is associative.} As already mentioned, the definition of morphisms in~\cite{igusa} is quite involved and in fact requires two technical lemmas proved in their own section (\cite[\S 2]{igusa}). From there, Igusa can show that his composition is associative. 

Without giving a formal proof, note that associativity is clear from
our description. Keeping the notations $f, g$ of
\cref{composition}, suppose we are given a third morphism $e$
with target $\pi$, \emph{i.e.} given by Schr\"oder trees indexed by
the blocks of $\pi$ (which also index vertices of $S(f)$). Then
associativity is equivalent to the fact that, if one substitutes first
$S(f)$ in $S(g)$, and then $S(e)$ in the tree $S(g\circ f)$, the
result is the same as substituting $S(e)$ in $S(f)$ and then
$S(f\circ e)$ in the tree $S(g)$. This is a rather clear property of
any kind of substitution in general.\bigskip

\noindent\textbf{$\NP_n$ is a cubical category}. The pictorial description of morphisms and their composition also sheds light on the results of \cite[\S 3]{igusa}. Given a morphism $f:\pi\to \mu$ in $\NP_n$, the category $Fac(f)$ has as objects all triples $(\xi,g,h)$ where $g:\pi\to \xi$, $h:\xi\to \mu$ and $f=h\circ g$, and a morphism  from $(\xi,g,h)$ to $(\xi',g',h')$ is a morphism $\phi:\xi\to \xi'$ such that $g'=\phi\circ g$ and $h'\circ \phi = h$.

We claim that $Fac(f)$ can be constructed as follows: Assume that $f$ is a morphism to the top of rank $k$, so that $S(f)$ is a tree with $k+1$ inner vertices. Pick any subset $E$ of the $k$ inner edges of $S(f)$. From $E$ a triple  $(\xi^E,g^E,h^E)$ of $Fac(f)$ can be constructed as follows: first $S(h^E)$ is obtained from $S(f)$ by contracting all edges in $E$, and this naturally determines $\xi^E$. Now, for each inner edge not in $E$, cut it so as to detach the lower vertex. In this manner $S(f)$ is cut into connected components which are naturally indexed by the blocks of $\xi^E$, and this determines the morphism $g^E$.

By the substitutive definition of composition, \emph{this procedure produces all objects of $Fac(f)$}. Also one has a morphism from $(\xi^E,g^E,h^E)$ to $(\xi^F,g^F,h^F)$ if and only if $E\subseteq F$, and this morphism is then unique. These results extend automatically to the case where $f$ is a general morphism.\medskip


It is then fairly easy to see that $\NP_n$ is a cubical category in the sense of~\cite[Definition 3.2]{igusa}. We mention only points (2) and (3) in this definition, the others being immediate. Point (2) states that $Fac(f)$ is isomorphic to the poset category of $\{1,\cdots,k\}$ ordered by inclusion, while point (3) demands that the forgetful functor $(\xi,g,h)\mapsto \xi$ from $Fac(f)$ to $\NP_n$ be an embedding. Both of these facts follow directly from the combinatorial description of $Fac(f)$.

\section{Enumerative aspects}
\label{sec_enum}

\subsection{Generating series for morphisms to the top}
\label{to_top}

Let us proceed to find generating series for the number of morphisms to the noncrossing partition with one block. We will use the Schr\"oder tree model for such morphisms, and we refer to \cref{directproof} for a proof based directly on Igusa's definition.

For this, one will use two parameters $z$ and $u$. The power of the
parameter $z$ records the number of angular sectors in the tree, which
is just $n$. The power of the parameter $u$ is the number of inner vertices
in the tree, which is the number $i$ of blocks in the source noncrossing partition $\pi$.

Let $\cQ$ be the class of nonempty  Schr\"oder trees  counted according to their number of angular sectors. $\cQ$ admits the recursive description
\begin{equation}
  \cQ = u (1+\cQ) \liste_{\geq 1}\left(\cZ (1+\cQ)\right),
\end{equation}
where $\cZ$ is the atom corresponding to an angular sector.

Let $Q=Q(z,u)$ be the generating function of the class $\cQ$. One therefore has the functional equation
\begin{equation}
  \label{eq_init_pour_Q}
  Q = \frac{u z (1+Q)^2 }{1-z(1+Q)}.
\end{equation}

By an algebraic manipulation, this is equivalent to the simpler equation
\begin{equation}
  \label{eq_pour_Q}  
  Q = z (1 + Q) (u + (1 + u) Q).
\end{equation}

\begin{remark}
  \label{directproof}
  Let us sketch another proof of~\eqref{eq_pour_Q} that does not use
  Schr\"oder trees.  Let $\cF_w$ (respectively $\cF_b$) be the class of
  bicolored plane trees rooted at a white (respectively black) vertex,
   enriched with a binary tree of size $d(w)$ for any white
  vertex. Note that $\cF_w$ is in fact the generating function for
  morphisms to the top by \cref{defi_morphisms}. We consider the
  associated generating functions $F_w,F_b$ where $z$ counts the
  number of edges and $u$ the number of black vertices. 

By decomposing at the root,  one has the relations
    $ F_b=\frac{u}{1-zF_w}$ and $F_w=C(z F_b)$.
  where $C(x)$ is the generating function for binary trees according
  to the number of vertices. Now $C$ satisfies $C=1/(1-xC)$ so we get $F_w=\frac{1}{1-zF_bF_w}$. Solving for $F_w$ gives the equation
$F_w=1+zF_w(uF_w+F_w-1)$, and so $F_w-1$ satisfies exactly the
  relation~\eqref{eq_pour_Q}.
\end{remark}



\subsection{Free probability computations}
\label{free_proba}

Recall the following transform, occurring in free probability under the
name of \emph{$R$-transform}, see for example~\cite{speicherSLC}. We let $R_n,M_n$ for $n\geq 1$ be two sequences (with values in a given ring) related by the following relations for $n\geq 1$:
\begin{equation}
  \label{def_M_depuis_R}
  M_n = \sum_{\pi \in \NC_n} R_{\pi},
\end{equation}
where $R_{\pi}$ is the product of $R_k$ for $k$
running over the block sizes of $\pi$.
Then the two generating functions
\begin{equation}
  R(z) = 1 + \sum_{n \geq 1} R_n z^n\quad\text{and}\quad  M(z) = 1 + \sum_{n \geq 1} M_n z^n
\end{equation}
are related by the equation
\begin{equation}
\label{Rtransform}
  M(z)=R(zM(z)).
\end{equation}

The proof is based on the following fact: a partition in $\NC_n$ has a unique decomposition into one block $\{i_1=1,i_2,\ldots,i_k\}$ containing $1$, and $k$  noncrossing partitions on the  intervals of integers $[i_j+1,i_{j+1}-1]$ for $j=1,\ldots ,k$ where $i_{k+1}=n+1$ by convention. Applying this decomposition to the terms in the right side of~\eqref{def_M_depuis_R}, one obtains the equality of the coefficients of $z^n$ on both sides of \eqref{Rtransform}.\medskip

Let us now apply this statement to the counting of all morphisms in
the category $\NP_n$. Define $\hom_n(i,j)$ to be the set of all morphisms in $\NP_n$ going from a noncrossing partition with $i$ blocks to a noncrossing partition with $j$ blocks. Recall that $Q_n(u)=[z^n]Q$ is a polynomial in $u$ counting morphisms to the top according to the number of blocks of the source partition. Equivalently, $Q_n$ is the coefficient of $v$ in the following polynomial
\begin{equation}
\label{defiMn}
  M_n(u,v):= \sum_{1\leq j \leq i \leq n} \#\hom_n(i,j) u^i v^j.
\end{equation}

Now the description of general morphisms in terms of morphisms to the top (cf. \cref{sub_morphisms} implies the following relations for $n\geq 1$:
\[
M_n(u,v)=\sum_{\pi=(\pi_1,\ldots,\pi_k)\in\NC_n}v^k Q_\pi
\]

\emph{Therefore the relations~\eqref{def_M_depuis_R} are satisfied with $M_n(u,v)$ and  $R_n(u,v):=vQ_n(u)$.} The corresponding generating function $R=R(z,u,v)$ is given by $R= 1 + vQ$, and satisfies
\begin{equation}
  \label{eq_pour_R}
  R = 1 + v z \left(1 + \frac{R - 1}{v}\right) \left(u + (1 + u) \frac{R - 1}{v}\right).
\end{equation}

by~\eqref{eq_pour_Q}. In this last equation, we perform the substitution $z\to zM$. We can then use  use the R-transform~\eqref{Rtransform} to get the following equation for $M$:
\begin{equation}
  \label{eq_pour_M}
  M = 1 + v z M \left(1 + \frac{M - 1}{v}\right) \left(u + (1 + u) \frac{M - 1}{v}\right).
\end{equation}

To simplify this functional equation, notice that by~ \eqref{defiMn} $uv$ divides $M_n$. It is natural to define $H$ as $\frac{M-1}{uvz}$, and substituting in~\eqref{eq_pour_M} gives immediately
\begin{equation}
  \label{eq_pour_H}
  H = \left(1 + uzH\right) \left(1 + uvzH\right) \left(1 + (1 + u)zH\right).
\end{equation}
Note that the coefficient $H_n$ of $z^n$ has the following expansion
\begin{equation*}
\label{defiHn}
  H_n = \sum_{0\leq j \leq i \leq {n-1}} \#\hom_{n+1}(i+1,j+1) u^i v^i.
\end{equation*}


\subsection{Hidden symmetry of order three}
\label{sub_symmetry} 

We prove the symmetry of order $3$ noticed in the introduction. First, let us substitute $u \mapsto 1/u$,   $v \mapsto 1/v$ and finally  $z \mapsto u v z $
in the equation~\eqref{eq_pour_H} for $H$. This gives us an equation for the generating series $\bL$ of the polynomials $\bL_n(u,v)$:
\begin{equation}
  \bL = (1 + z\bL)(1 + vz \bL) (1 + (1 + u) vz \bL).
\end{equation}
Let us now perform the substitution $u\mapsto u-1$
to obtain an equation for the generating series $\Delta$ of the polynomials $\Delta_n(u,v)$:
\begin{equation}
  \Delta = (1 + z\Delta) (1 + v z \Delta)(1+ u v z \Delta),
\end{equation}
The transformations for $\Delta_n(u,v)$ given in the introduction are immediately deduced from this functional equation, which describes ternary rooted trees according to their total number of edges, where $v$ is accounting for left edges and $u v$ is accounting for right edges. This has an evident invariance under the symmetric group of order $3$, permuting the three kinds of edges (namely left, middle and right). 

\subsection{Proof of \cref{th:refined_enumeration}}
Let us now proceed to compute the cardinalities $\#\hom_n(i,j)$ by Lagrange inversion. Let $L = uzH$ so that $[u^i v^j z^n] L=\#\hom_n(i,j+1)$. From~\eqref{eq_pour_H}, one gets
\begin{equation}
  \frac{L}{(1+ v L)(1+L)(u + (1 + u) L)} = z.
\end{equation}

Setting $\phi(w) = (1+w)(1+v w)(w+u(1+w))$, Lagrange inversion theorem says that
\begin{equation*}
  [z^n] L = \frac{1}{n}[w^{n-1}]\left( \phi(w)^n \right).
\end{equation*}
This implies that
\begin{equation*}
  [u^i v^j z^n] L = \frac{1}{n} [w^{n-1}] \left((1+w)^n \binom{n}{j} w^j \binom{n}{i} (1+w)^i w^{n-i}\right).
\end{equation*}
From there, one gets
\begin{equation}
  \label{brut_L}
  [u^i v^j z^n] L = \frac{1}{n}\binom{n}{i}\binom{n}{j}\binom{n+i}{i-j-1}.
\end{equation}

This proves \cref{th:refined_enumeration} since $\ell_{i,j}=\#\hom_n(n-j,n-i)$ by definition.


\printbibliography

\end{document}
